We introduce an algorithm design technique for a class of combinatorialoptimization problems with concave costs. This technique yields a stronglypolynomial primal-dual algorithm for a concave cost problem whenever such analgorithm exists for the fixed-charge counterpart of the problem. For manypractical concave cost problems, the fixed-charge counterpart is a well-studiedcombinatorial optimization problem. Our technique preserves constant factorapproximation ratios, as well as ratios that depend only on certain problemparameters, and exact algorithms yield exact algorithms. Using our technique, we obtain a new 1.61-approximation algorithm for theconcave cost facility location problem. For inventory problems, we obtain a newexact algorithm for the economic lot-sizing problem with general concaveordering costs, and a 4-approximation algorithm for the joint replenishmentproblem with general concave individual ordering costs.
展开▼
